function quickSort(arr, left = 0, right = arr.length - 1) {
  // 如果只有一个元素，则没有排序必要
  if (arr.length > 1) {
    // splitIdx表示下一分割左右子数组的索引
    const splitIdx = partition(arr, left, right)
    // 左子数组大于一个元素，才继续递归分割排序
    if (splitIdx > left + 1) {
      // 左子数组以splitIdx - 1作为左边界
      quickSort(arr, left, splitIdx - 1)
    }
    // 右子数组大于一个元素，才继续递归分割排序
    if (splitIdx < right) {
      quickSort(arr, splitIdx, right)
    }
  }
  return arr
}

// 以基准值为中心，划分左右子数组
function partition(arr, left, right) {
  // 取中间的值作为基准值
  let coreValue = arr[Math.floor(left + (right - left) / 2)]
  // 初始化左右指针
  let i = left,
    j = right
  // 左右指针没有越界
  while (i <= j) {
    // 左指针寻找不小于基准值的元素
    while (arr[i] < coreValue) {
      i++
    }
    // 右指针寻找不大于基准值的元素
    while (arr[j] > coreValue) {
      j--
    }
    // 左/右指针存在符合条件的元素，则交换他们
    if (i <= j) {
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
      i++
      j--
    }
  }
  // 将左指针的索引返回，接着进行划分左右子数组操作
  return i
}
let testArr = [9, 8, 7, 6, 5]
let res = quickSort(testArr)
console.log(res)
